/**
 * @file     binarySearch.js
 * @brief    [704. 二分查找](https://leetcode.cn/problems/binary-search/description/)
 * @author   Zhu
 * @date     2023-06-05 20:25
 */

/**
 * 递归
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    function bisect(l, r) {
        if (l > r) return -1;
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return bisect(l, mid - 1);
        } else {
            return bisect(mid + 1, r);
        }
    }

    return bisect(0, nums.length - 1);
};

/**
 * 迭代
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let i = 0,
        j = nums.length - 1;
    while (i <= j) {
        let mid = Math.floor((i + j) / 2);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }

    return -1;
};
